Various methods are employed to increase data durability of data in a relational database management system, a non-relational data storage system, or other distributed data storage system or distributed database. In large scale distributed data storage systems, redundant replication, where multiple copies of a data object are stored in multiple nodes of a distributed data storage system, which can also be disparately located across multiple data centers, can be employed to increase data durability. The storage costs of employing a redundant replication scheme as the amount and number of data objects in the distributed data storage system grows can be quite high.